#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <vector>
//class Solution {
//public:
//    int ret;
//    int memo;
//    int lengthOfLIS(vector<int>& nums) {
//        ret = 0;
//        for (int i = 0; i < nums.size(); i++)
//        {
//            memo = nums[i];
//            int ret1 = dfs(nums, i);
//            if (ret1 > ret)
//                ret = ret1;
//        }
//        return ret;
//    }
//    int dfs(vector<int>& nums, int i)
//    {
//        if (i == nums.size())
//        {
//            return 0;
//        }
//        if (i == 0)
//        {
//            //memo = nums[i];
//            return dfs(nums, i + 1) + 1;
//        }
//        else if (nums[i] > memo)
//        {
//            memo = nums[i];
//            return dfs(nums, i + 1) + 1;
//        }
//        return dfs(nums, i + 1);
//    }
//
//};
//
//
//class Solution {
//public:
//    int ret;
//    int memo;
//    int lengthOfLIS(vector<int>& nums) {
//        vector<int> memo(nums.size());
//        ret = 0;
//        for (int i = 0; i < nums.size(); i++)
//        {
//            int ret1 = dfs(memo, nums, i);
//            if (ret1 > ret)
//                ret = ret1;
//        }
//        return ret;
//    }
//    int dfs(vector<int>& memo, vector<int>& nums, int pos)
//    {
//
//        if (pos == nums.size())
//        {
//            return 0;
//        }
//        if (memo[pos] != 0)
//            return memo[pos];
//        int ret = 1;
//        for (int i = pos + 1; i < nums.size(); i++)
//        {
//            if (nums[i] > nums[pos])
//            {
//                ret = max(ret, dfs(memo, nums, i) + 1);
//            }
//        }
//        memo[pos] = ret;
//        return memo[pos];
//    }
//
//};
//int ret = 0;
//int lengthOfLIS(vector<int>& nums) {
//    vector<int> memo(nums.size());
//    memo[nums.size() - 1] = 1;
//    for (int i = nums.size() - 2; i >= 0; i--)
//    {
//        for (int j = i + 1; j < nums.size(); j++)
//        {
//            if (memo[i] < memo[j])
//                memo[i] = max(memo[i], memo[j]);
//        }
//        memo[i]++;
//        ret = max(ret, memo[i]);
//    }
//    return ret;
//}
//class Solution {
//public:
//    int getMoneyAmount(int n) {
//        return dfs(1, n);
//    }
//    int dfs(int begin, int end)
//    {
//        if (end - begin <= 1)
//        {
//            return 0;
//        }
//        int left = INT_MAX;
//        int right = INT_MAX;
//        for (int i = begin; i <= end; i++)
//        {
//            left = min(dfs(begin, i - 1) + i, left);
//            right = min(dfs(i + 1, end) + i, right);
//        }
//        return max(left, right);
//    }
//};


class Solution {
public:
    int m, n;
    vector<vector<int>> memo;
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        m = matrix.size();
        n = matrix[0].size();
        memo.resize(n + 1, vector<int>(n + 1));
        int ret = 1;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                ret = max(dfs(matrix, i, j), ret);
            }
        }
        return ret;
    }
    int dfs(vector<vector<int>> matrix, int i, int j)
    {
        if (memo[i][j] != 0)
            return memo[i][j];
        int ret = 0;
        for (int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = dy[k] + j;
            if (x >= 0 && x < m && y >= 0 && y<n && matrix[x][y]>matrix[i][j])
            {
                ret = max(dfs(matrix, x, y) + 1, ret);
            }
        }
        memo[i][j] = ret;
        return ret;
    }
};
int main()
{
    Solution s;
    vector<vector<int>> nums = { {0} ,{1},{5},{5} };
    s.longestIncreasingPath(nums);
    //s.getMoneyAmount(10);
    //vector<int> nums = { 10,9,2,5,3,7,101,18 };
    //lengthOfLIS(nums);
    return 0;
}
//class Solution {
//public:
//    int ret = 0;
//    int lengthOfLIS(vector<int>& nums) {
//        vector<int> memo(nums.size());
//        if (nums.size() == 1)
//            return 1;
//        memo[nums.size() - 1] = 1;
//        for (int i = nums.size() - 2; i >= 0; i--)
//        {
//            for (int j = i + 1; j < nums.size(); j++)
//            {
//                if (nums[i] < nums[j])
//                    memo[i] = max(memo[i], memo[j]);
//            }
//            memo[i]++;
//            ret = max(ret, memo[i]);
//        }
//        return ret;
//    }
//
//};

//class Solution {
//public:
//    int getMoneyAmount(int n) {
//        vector<vector<int>> memo(n + 1, vector<int>(n + 1));
//        return dfs(memo, 1, n);
//    }
//    int dfs(vector<vector<int>>& memo, int begin, int end)
//    {
//        if (begin >= end)
//        {
//            return 0;
//        }
//        if (memo[begin][end] != 0)
//            return memo[begin][end];
//        int left = INT_MAX;
//        int right = INT_MAX;
//        int ret = INT_MAX;
//        for (int i = begin; i <= end; i++)
//        {
//            left = dfs(memo, begin, i - 1);
//            right = dfs(memo, i + 1, end);
//            ret = min(ret, i + max(left, right));
//            if (i - 1 >= 1)
//                memo[begin][i - 1] = left;
//            if (i + 1 <= end)
//                memo[i + 1][end] = right;
//        }
//        return ret;
//    }
//};